package recursion;

/**
 * Suppose a rabbit is hopping on a 2-dimensional integer lattice. 
 * It can only go right or up by one step at a time. The rabbit starts at (0,0),
 * how many paths are there for it to reach (n, n)
 *  
 * 
 * @author Lei
 */
public class FindPathsInMatrix {

    public static int findPathsInMatrix(int m, int n) {

        if (m < 0 || n < 0) {
            return 0;
        }

        if (m == 0 && n == 0) {
            return 0;
        }
        if (m == 0 && n == 1) {
            return 1;
        }
        if (m == 1 && n == 0) {
            return 1;
        }
        return findPathsInMatrix(m - 1, n) + findPathsInMatrix(m, n - 1);
    }

    public static void main(String[] args) {
        System.out.println(FindPathsInMatrix.findPathsInMatrix(5, 5));
    }
}
